package test.n00100;


import java.util.Arrays;

public class Problem00142 {
    public static void main(String[] args) {
        println(new String[]{"flower", "flow", "flight"});
        println(new String[]{"dog", "racecar", "car"});
        println(new String[]{"reflower", "flow", "flight"});
    }

    public static void println(String[] strs) {
        Solution ss = new Solution();
        System.out.println(Arrays.asList(strs) + "," + ss.longestCommonPrefix(strs));
    }

    public static class Solution {

        /**
         * 编写一个函数来查找字符串数组中的最长公共前缀。
         * <p>
         * 如果不存在公共前缀，返回空字符串 ""。
         * <p>
         * 提示：
         * <p>
         * 1 <= strs.length <= 200
         * 0 <= strs[i].length <= 200
         * strs[i] 仅由小写英文字母组成
         *
         * @param strs
         * @return
         */
        public String longestCommonPrefix(String[] strs) {
            String minLengthStr = strs[0];
            for (String s : strs) {
                if (minLengthStr.length() > s.length()) {
                    minLengthStr = s;
                }
            }


//            int len = minLengthStr.length();
//            String[] matrix = new String[(1 + len) * len / 2];
//            int p = 0;
//            for (int i = 0; i < len; i++) {
//                for (int j = i + 1; j < len + 1; j++) {
//                    matrix[p++] = minLengthStr.substring(i, j);
//                }
//            }

            int len = minLengthStr.length();
            String[] matrix = new String[len];
            for (int i = 0; i < len; i++) {
                matrix[i] = minLengthStr.substring(0, i + 1);
            }

            String r = "";
            for (String c : matrix) {
                boolean flag = true;
                for (String s : strs) {
                    if (!s.startsWith(c)) {
                        flag = false;
                        break;
                    }
                }

                if (flag && c.length() > r.length()) {
                    r = c;
                }
            }
            return r;
        }
    }
}
